package leetcode.code1277;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

public class Solution2 implements IDebug {

	public int countSquares(int[][] matrix) {
		int ans = 0;
		int m = matrix.length, n = matrix[0].length;
		int max = Math.max(m, n);
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				if (matrix[i][j] == 1) {
					ans++;
				}
			}
		}
		for (int k = 1; k <= max; k++) {
			int next = k + 1;
			for (int i = k; i < m; i++) {
				for (int j = k; j < n; j++) {
					if (matrix[i][j] >= k && matrix[i - 1][j] >= k && matrix[i][j - 1] >= k
							&& matrix[i - 1][j - 1] >= k) {
						ans++;
						matrix[i][j] = next;
					}
				}
			}
		}
		HelpDebug.print(matrix);
		return ans;
	}

	@Override
	public void debug1() {
		HelpDebug.compare(15, this.countSquares(HelpDebug.str2array1("[[0,1,1,1],[1,1,1,1],[0,1,1,1]]")));

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution2 so = new Solution2();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
